Network adapters in network switching nodes are used to connect the network physical links to the node's switch element. With current electronic technology it is hard to implement low cost searching functions in the adapters when the bit fields to be searched are large and the processing time must be limited in order to sustain the high network link media speeds.
The trend today is to use Asynchronous Transfer Mode as high speed transmission and switching communication networks. In ATM networks, all data are transported in cells and each cell is 53 bytes long. The first five bytes contain a header for identification of the cell. Particularly, the header contains a VPI/VCI (Virtual Channel Identifier/Virtual Path Identifier) field conforming to the ITU-T standardization of the `integrated services digital network (B-ISDN)` I.361, last update 11/95. A contiguous field of 128 addresses encoded in 7 bits could, following the I.361 recommendation, be in a range of 128-255 or 1024-1151 or any contiguous field for which the seven least significant bits range from 0 to 127. The length of the VPI/VCI field of the ATM cell header is either 24 bits or 28 bits depending on the type of interface (User Network Interface or Network Node Interface). Each VPI/VCI field identifies a virtual connection that the cell belongs to. The I.361 recommendation requires that the bits allocated to the VPI and VCI bit field be contiguous.
In ATM networks connections are defined from one end of the network to the other end but, the VPI/VCI connection identification has only local significance between any two nodes. As a consequence, for routing of an ATM cell received at an input link port of a switching node, the VPI/VCI field is read and replaced (swapped) by a new field retrieved from a table stored in the node. A routing tag is attached so that the cell can be routed through the switch. After switching, the routing tag is removed and the cell is transmitted on proper outgoing link with the new VPI/VCI field. For routing each cell, the VPI/VCI bit field of the cell header is read and a table is searched for a match. The match entry contains the matched VPI/VCI field and the new VIP/VCI field or a pointer towards this final field. The table search has to be efficient because in adapters handling high speed links have limited cell processing time. The network manager also accesses the table for creating and deleting entries at each creation or deletion of a connection. Efficient table searches are important when updates are being made as well as when the table is being used for routing.
It is not realistic to create a table having as many stored entries as the number of possible combinations of the VPI/VCI field because for a VPI/VCI field of 28 bits, there are 2.sup.28 =268.times.10.sup.6 possible combinations. However, according to the ITU specifications referenced above, the VCI and VPI bit fields are continuously allocated. The continuous bit allocation for VPI or VCI can be any part of the respective 8/12 and 16 bit fields. The bit allocation is negotiated between the user and the network manager at connection setup. That is why the search function should cover any of the possible combinations of 24/28 bits. In practice, the number of entries used is the number of simultaneous connections supported by the adapter. Typically about 2000 connections per link and about 4 high speed links are supported by an adapter, giving a total of 8000 connections or table entries per adapter. Consequently, one alternative to maximum table of 2.sup.24 or 2.sup.28 entries, would be a table of 8000 entries to be sequentially read each time a cell header is swapped. This solution is inefficient because of the poor performance of a sequential searching operation.
One conventional way of achieving high speed searching of large bit fields by using a CAM (Content Addressable Memory) hardware device. CAM components are available in the networking industry and operate as follows. A key is given as an input and the result of the search is provided in a time quite acceptable for high speed ATM cell processing. However, current CAM components have typically only 1 k entries and are very expensive.
To reduce costs, a solution taught in European patent application EP 94480033.3 is to use three or more cascaded DRAM storage units as a `pseudo-CAM`, using parts of the initial bit fields combined with the result read in a previous table as a key to the next table. This solution implies the use of at least 3.times.16 Mbit DRAM storage units for handling 8000 simultaneous connections. The cost of such a `pseudo-CAM` to implement a search function, although lower than a conventional CAM, must be further reduced to be satisfactory for use in network adapters.
One other solution for an efficient searching function is to use a binary tree based search or hash function. A problem of binary trees is that they are difficult to manage. The DELETE and CREATE entry operations are much too complex. When using a hash function f, for a given entry address to be searched, E (in our case a 2.sup.24 or 2.sup.28 bit field address) is associated with a computed key, f(E), which is used as the table address which is pointed to and from which a second search begins among a subset of addresses. A good hash function is one which has a simple key computation and which splits the original addressed to be searched into bounded, non-intersecting subsets of addresses of about the same size. These conditions are described as producing no clustering of data. Volume 3 of the publication `The Art of Computer Programming` of Donald E. Knut, Addison Wesley Publishing Company, 1973, page 513, suggests that the computation of the hash key comprise algebraic operations instead of arithmetic operations. The hash key could be obtained by dividing the initial address polynomial representation by a polynomial modulo 2. At page 519 of the same publication, it is also suggested a sequential search be made in the subsets selected by the hash key. When trying to find the address corresponding to the entry address E, the key f(E) is computed with the hash function and the first entry address is read sequentially until either finding the entry address E or finding an empty position. This `linear probing` scheme is however only practicable if there is no clustering of data.
It is an object of the invention to provide a low cost method and device for implementing a searching function where processing time is limited.
It is a second object of the invention to have simple, efficient management of address entries to allow simple deletion and addition of stored values, for instance, connection VPI/VCI values in the case of ATM processing.
A third object of the invention is to provide a solution that can be implemented either as hardware or software. In the example of the ATM adapter, the search function could be a hardware-assisted implementation or a software application operating on a processor already programmed to perform other software functions in the adapter.